import java.util.Stack;


public class Recursive {

	// N階乘模擬遞迴
	public static void stTypeF(int limit, int n) {
		int prev_child = -1;
		int next_child = -1;
		Stack<Integer> stack = new Stack<Integer>();

		do {
			if(stack.size()==limit) {
				// 顯示階段性結果
				for(int i=0;i<limit;i++) {
					System.out.print(stack.get(i)+" ");
				}
				System.out.println();
				prev_child = stack.pop();
			} else {
				next_child = -1;
				for(int i=prev_child+1;i<n;i++) {
					if(!stack.contains(i)) {
						next_child = i;
						break;
					}
				}
				if(next_child==-1) {
					prev_child = stack.pop();
				} else {
					stack.push(next_child);
					prev_child = -1;
				}
			}
		} while(stack.size()!=0||next_child==-1);
	}
	
	// N階乘遞迴 (跑 depth! 次, 不算判斷式迴圈的部份)
	public static void rsTypeF(int depth, int limit, int n, int[] data) {
		if(depth==limit) {
			for(int i=0;i<limit;i++) {
				System.out.print(data[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=0;i<n;i++) {
			boolean existed = false;
			// 這個迴圈沒算進 BigO (表面上看起來是 n! 但是判斷式也要跑 <depth 遍, 數學歸納法)
			for(int j=0;j<depth;j++) {
				if(i==data[j]) {
					existed = true;
					break;
				}
			}
			if(!existed) {
				data[depth] = i;
				rsTypeF(depth+1,limit,n,data);
			}
		}
	}
	
	// N子的模擬遞迴
	public static void stTypeN(int limit, int n) {
		int prev_child = -1;
		int tail_child = n-1;
		Stack<Integer> stack = new Stack<Integer>();

		do {
			if(stack.size()==limit) {
				// 顯示階段性結果
				for(int i=0;i<limit;i++) {
					System.out.print(stack.get(i)+" ");
				}
				System.out.println();
				prev_child = stack.pop();
			} else {
				if(prev_child==tail_child) {
					prev_child = stack.pop();
				} else {
					stack.push(prev_child+1);
					prev_child = -1;
				}
			}
		} while(stack.size()!=0||prev_child!=tail_child);
	}
	
	// N子遞迴 (跑 n^depth 次)
	public static void rsTypeN(int depth, int limit, int n, int[] data) {
		if(depth==limit) {
			for(int i=0;i<limit;i++) {
				System.out.print(data[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=0;i<n;i++) {
			data[depth] = i;
			rsTypeN(depth+1,limit,n,data);
		}
	}
	
	// 2子的模擬遞迴
	public static void stType2(int limit) {
		int prev_child = -1;
		Stack<Integer> stack = new Stack<Integer>();

		do {		
			if(stack.size()==limit) {
				// 顯示階段性結果
				for(int i=0;i<limit;i++) {
					System.out.print(stack.get(i)+" ");
				}
				System.out.println();
				prev_child = stack.pop();
			} else {
				if(prev_child==1) {
					prev_child = stack.pop();
				} else {
					stack.push(prev_child+1);
					prev_child = -1;
				}
			}
		} while(stack.size()!=0||prev_child!=1);
	}

	// 2子的遞迴 (跑 2^depth 次)
	public static void rsType2(int depth, int limit, int[] data) {
		if(depth==limit) {
			for(int i=0;i<limit;i++) {
				System.out.print(data[i]+" ");
			}
			System.out.println();
			return;
		}
		data[depth] = 0;
		rsType2(depth+1,limit,data);
		data[depth] = 1;
		rsType2(depth+1,limit,data);
	}
	
	// 1子模擬遞迴
	public static void stType1(int limit) {
		Stack<Integer> stack = new Stack<Integer>();

		do {
			stack.push(stack.size());
		} while(stack.size()<limit);

		for(int i=0;i<limit;i++) {
			System.out.print(stack.get(i)+" ");
		}
		System.out.println();
	}
	
	// 1子的遞迴 (跑 depth 次)
	public static void rsType1(int depth, int limit, int[] data) {
		if(depth==limit) {
			for(int i=0;i<limit;i++) {
				System.out.print(data[i]+" ");
			}
			System.out.println();
			return;
		}
		data[depth] = depth;
		rsType1(depth+1,limit,data);
	}
	
	public static void main(String[] args) {
		int[] data = new int[5];
		System.out.println("獨子遞迴測試");
		rsType1(0,5,data);
		System.out.println("雙子遞迴測試");
		rsType2(0,3,data);
		System.out.println("N子遞迴測試");
		rsTypeN(0,3,3,data);
		System.out.println("N階乘遞迴測試");
		rsTypeF(0,3,3,data);

		System.out.println("獨子模擬遞迴測試");
		stType1(5);
		System.out.println("雙子模擬遞迴測試");
		stType2(3);
		System.out.println("N子模擬遞迴測試");
		stTypeN(3,3);
		System.out.println("N階乘模擬遞迴測試");
		stTypeF(3,3);
	}

}
